#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
using namespace std;

// class Solution {
// public:
//     bool canCross(vector<int>& stones) {
//         //先把stones里面的内容存在map里面
//         map<int,int> M;
//         for(int i = 0;i<stones.size();++i){
//             M[stones[i]] = i;
//         }
//         return func(stones,M,0,0);



//     }
//     bool func(vector<int>& stones,map<int,int>& M,int pre,int index){
//         //掉河里了
//         if(M.find(index)==M.end()){
//             return false;
//         }
//         if(pre==index&&pre!=0){
//             return false;
//         }
//         if(M[index]==stones.size()-1){
//             return true;
//         }
//         pre = index - pre; //上一次跳的距离
//         if(pre == 0){
//             return func(stones,M,0,1);
//         }
//         else{
//             return func(stones,M,index,index+pre+1)||func(stones,M,index,index+pre)||func(stones,M,index,index+pre-1);
//         }
//         return false;
//     }
// };

//递归超时,只能用动态规划做
class Solution {
public:                                     
    bool canCross(vector<int>& stones) {                                                                                                          
        if(stones[1]!=1){
            return false;
        }
        //dp[i]表示要跳到这块stones[i]石头上的pre
        vector<set<int>> dp(stones.size(),set<int>{});
        dp[1].insert(1);
        for(int i =2;i<stones.size();++i){
            for(int j=i-1;j>=1;--j){
                int temp = stones[i]-stones[j];
                if(dp[j].find(temp)!=dp[j].end()||dp[j].find(temp+1)!=dp[j].end()||dp[j].find(temp-1)!=dp[j].end()){
                    dp[i].insert(temp);
                }
                }
            }
        
        return (dp[stones.size()-1].empty())? false: true;
    }
};
int main(){
    Solution S;
    vector<int> stones = {0,1,2,3,4,8,9,11};
    cout<<S.canCross(stones)<<endl;
}